package
{
	import flash.display.Sprite;
	import flash.geom.Point;
	import flash.geom.Rectangle;

	public class SkipQuadtree
	{
		public static const DOT_SIZE:Number = 1.5
		public static const LINE_SIZE:Number= 1.0;
		public static const IMAGE_SIZE:int = 600;		
		public static const SMALL_SIZE:int = 100;
		public static const MAX_INT:Rectangle = new Rectangle(int.MIN_VALUE, int.MIN_VALUE, (int.MAX_VALUE - int.MIN_VALUE), (int.MAX_VALUE - int.MIN_VALUE));
		public static const MAX_NUMBER:Rectangle = new Rectangle(-Number.MAX_VALUE/8, -Number.MAX_VALUE/8, Number.MAX_VALUE/4, Number.MAX_VALUE/4);
		public static const SMALLER:Rectangle = new Rectangle(-SMALL_SIZE, -SMALL_SIZE, SMALL_SIZE*2, SMALL_SIZE*2);
		public static const QUAD_SIZE:Rectangle = SMALLER;
		public var root:QuadNode;
		private var m_height:int;
	
		
		public function SkipQuadtree(compressed:Boolean = false)
		{
			
			var i:int;
			root = new QuadNode(0,compressed);
			root.boundingBox = QUAD_SIZE;
			root.children = createQuadChildren(root.boundingBox, root.depth + 1, compressed);
			m_height = 0;
		}
		
		public function getDepth():int{
			return root.getMaxDepth();
		}
		
		public function insert(point:Point):void{
			root.insert(point);
		}
		
		public function find(point:Point):Boolean{
			return root.find(point);
		}
		
		public function remove(point:Point):void{
			root.remove(point,1);	
		}
		
		public function createImage():Sprite{
			return root.createImage();
		}
		
		
		public static function drawTree(quadNode:QuadNode, size:Number):Sprite{
			var rect:Rectangle = quadNode.boundingBox;
			var imageSize:Number = size/(Math.pow(2,quadNode.depth));
			var normilizationFactor:Point = new Point(imageSize / rect.width, imageSize / rect.height);
			var box:Sprite = new Sprite();
			
			if(!quadNode.children){
				var color:uint = rect.topLeft.length * normilizationFactor.length * 0xffffff * rect.size.length * normilizationFactor.length;
				box.graphics.beginFill(color);
				box.graphics.drawRect(rect.x * normilizationFactor.x, 
					rect.y * normilizationFactor.y, 
					rect.width * normilizationFactor.x, 
					rect.height * normilizationFactor.y);
				box.graphics.endFill();
			}
			
			box.graphics.lineStyle(LINE_SIZE);
			
			box.graphics.moveTo(rect.left * normilizationFactor.x, rect.bottom*normilizationFactor.y);
			box.graphics.lineTo(rect.left * normilizationFactor.x, rect.top*normilizationFactor.y);
			box.graphics.lineTo(rect.right* normilizationFactor.x, rect.top*normilizationFactor.y);
			box.graphics.lineTo(rect.right* normilizationFactor.x, rect.bottom*normilizationFactor.y);
			box.graphics.lineTo(rect.left * normilizationFactor.x, rect.bottom*normilizationFactor.y);
			
			if(quadNode.point != null){
				var dot:Sprite = new Sprite();
				dot.graphics.beginFill(0);
				dot.graphics.drawCircle(quadNode.point.x * normilizationFactor.x, quadNode.point.y * normilizationFactor.y,DOT_SIZE);
				dot.graphics.endFill();
				box.addChild(dot);
			}
			for each(var child:QuadNode in quadNode.children){
				var childSprite:Sprite = drawTree(child, size);
				box.addChild(childSprite);
			}
			
			return box;
		}
				
		

		public static function createQuadChildren(boundingBox:Rectangle, depth:int = 0, compressed:Boolean = false):Vector.<QuadNode>{
			var child:QuadNode;
			var children:Vector.<QuadNode> = new Vector.<QuadNode>;
			
			// top left
			child = new QuadNode(depth,compressed);
			child.boundingBox = new Rectangle(boundingBox.left, 
				boundingBox.top, 
				boundingBox.width/2,
				boundingBox.height/2);
			children.push(child);
			
			// top right
			child = new QuadNode(depth,compressed);
			child.boundingBox = new Rectangle(boundingBox.left + boundingBox.width/2, 
				boundingBox.top, 
				boundingBox.width/2, 
				boundingBox.height/2);
			children.push(child);
			
			// bottom left
			child = new QuadNode(depth,compressed);
			child.boundingBox = new Rectangle(boundingBox.left, 
				boundingBox.top + boundingBox.height/2, 
				boundingBox.width/2, 
				boundingBox.height/2);
			children.push(child);
			
			// bottom right
			child = new QuadNode(depth,compressed);
			child.boundingBox = new Rectangle(boundingBox.left + boundingBox.width/2, 
				boundingBox.top + boundingBox.height/2, 
				boundingBox.width/2, 
				boundingBox.height/2);
			children.push(child);			
			
			return children;
		}
	}
}